package leetcode.code1042;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int[] gardenNoAdj(int n, int[][] paths) {
		Map<Integer, List<Integer>> edges = new HashMap<>();
		for (int i = 0; i < paths.length; i++) {
			int x = paths[i][0], y = paths[i][1];
			edges.computeIfAbsent(x, key -> new ArrayList<>()).add(y);
			edges.computeIfAbsent(y, key -> new ArrayList<>()).add(x);
		}
		int[] ans = new int[n];
		boolean[] done = new boolean[n];
		for (int i = 0; i < ans.length; i++) {
			if (!done[i]) {
				this.f(ans, done, i, edges);
			}
		}
		return ans;
	}

	private void f(int[] ans, boolean[] done, int index, Map<Integer, List<Integer>> edges) {
		done[index] = true;
		int color = 0;
		for (int i = 0; i < 4; i++) {
			if ((ans[index] & (1 << i)) == 0) {
				color = i + 1;
				break;
			}
		}
		ans[index] = color;
		List<Integer> nexts = edges.get(index + 1);
		if (nexts != null) {
			for (int next : nexts) {
				if (!done[next - 1]) {
					ans[next - 1] |= 1 << (color - 1);
				}
			}
			for (int next : nexts) {
				if (!done[next - 1]) {
					this.f(ans, done, next - 1, edges);
				}
			}
		}
	}

	// 双向邻接矩阵，哈希邻接列表
	public Map<Integer, List<Integer>> edges(int[][] paths) {
		Map<Integer, List<Integer>> edges = new HashMap<>();
		for (int i = 0; i < paths.length; i++) {
			int x = paths[i][0], y = paths[i][1];
			edges.computeIfAbsent(x, key -> new ArrayList<>()).add(y);
			edges.computeIfAbsent(y, key -> new ArrayList<>()).add(x);
		}
		return edges;
	}

	@Override
	public void debug4() {
		H.compare(H.str2array3("[1,2,2,1,3,2]"),
				this.gardenNoAdj(6, H.str2array1("[[6,4],[6,1],[3,1],[4,5],[2,1],[5,6],[5,2]]")));
		H.compare(H.str2array3("[1,2,3,4]"),
				this.gardenNoAdj(4, H.str2array1("[[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
